A communication network comprises nodes connected by links. A node refers to a network element implementing a protocol used for communicating with other nodes. A link refers to a communication facility or medium over which nodes can communicate. A communication network may either be connectionless such as an IP-based (Internet Protocol) network, or connection-oriented such as a fixed telephone network. When a traffic flow comprising data packets is transmitted from a given source node to a given destination node, there are often multiple different routes available via various nodes and links between the source and destination node. These routes are referred to as paths. In the following the term path is used to refer specifically to a loop-free path.
Different paths have different costs associated with them. For example, a given path may have higher delay than another path. Thus it is advantageous to determine these costs beforehand and select a path based on this information. Since a traffic flow comprising packets may be distributed via multiple paths simultaneously, more than one paths may also be selected.
The process of determining costs and selecting paths is often referred to as load distribution. Load in this context refers to the amount of packets or bytes being transferred over nodes and links thus loading them. Distributing traffic flows over multiple paths in a communication network has several advantages, such as fast failure recovery due to pre-existence of multiple available paths between source and destination, higher throughput for a given infrastructure and reduced packet delay. Load distribution may be static, in which case assignment of jobs to hosts is done probabilistically or deterministically, without consideration of runtime events. Alternatively load distribution may be dynamic, in which case it is designed to overcome problems of unknown or uncharacteriseable workloads, non-pervasive scheduling and runtime variation, i.e. any situation where availability of hosts, composition of workload or interaction of human beings can alter resource requirements or availability. Dynamic load distribution systems typically monitor workload and hosts for any factors that may affect the choice of the most appropriate assignment and distribute jobs accordingly.
A prior art method of static load distributing based on cost optimization is based on an estimate of static traffic demand between all node pairs and a weight function that is a decreasing function of the load over a link. Optimizing is performed using this heuristic cost function so that the cost of the total network is minimal, i.e. throughput through the network is optimized. The usefulness of the method is completely dependent on the accuracy of the traffic demand estimates.
A prior art method of dynamic load distributing based on cost adjustment is generally referred to as Optimized Multi Path. Costs associated with links are slowly changed based on changes of network state parameters. If OSPF-protocol (Open Shortest Path First) is used in connection with Optimized Multi Path, information about the changes is disseminated in opaque LSAs (Link State Advertisement). Adjustments in link costs are made gradually enough to insure stability, yet to provide reasonably fast reaction to traffic demands. Paths between two nodes are based on the adjusted costs, so the paths may change over time.
There are problems with prior art load distributing. Mechanisms that efficiently distribute traffic generally require network-wide state information to optimize or adjust path selection. These mechanisms use state information collected over varying time scales. Therefore they are reactive and operate on an hours to days time scale. Load distribution mechanisms that do not affect the paths between source and destination, on the other hand, distribute the load in a node over the available paths optionally including the costs of available paths. These mechanisms do not consider state information other than that which they may have themselves. Another problem associated with dynamic load distribution is maintaining flow integrity at all times. If flow integrity is not maintained, packet re-ordering generally occurs. In the case of TCP-based (Transmission Control Protocol) traffic this will reduce throughput considerably, whereas in the case of UDP-based (User Datagram Protocol) traffic applications may not be able to recover from packet reversal.
Thus there is obvious need for a solution providing efficient dynamic load distribution using local state information in a communication network as well as using information of the neighbors to improve efficiency by taking into account the local environment.